package jianzhioffer;

import com.sun.javafx.logging.JFRInputEvent;

public class MaxSubArray {


    // 暴力 -- 超时了
    public int maxSubArray1(int[] nums) {

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum > res) {
                    res = sum;
                }
            }
        }
        return res;
    }


    // 分治

    /**
     * 一般分治都配合二分
     * 思想：
     * 一个元素的时候，直接输出
     * 多于一个的时候，考虑三种情况。
     * 1、最大子序列在左侧。[0,mid]
     * 2、在右侧 [mid+1,n-1]
     * 3、横跨左右两侧（差不多在中间）
     *
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        int n = nums.length;
        return maxSubSum(nums, 0, n - 1);

    }

    // TODO
    private int maxSubSum(int[] nums, int left, int right) {
        if (left == right) {
            return Math.max(nums[left], 0);
        }
        int mid = (left + right) >> 1;
        int maxLeftSum = maxSubSum(nums, left, mid);
        int maxRightSum = maxSubSum(nums, mid + 1, right);
        // 求出左边加上数组元素的和
        int maxLeftBorderSum = 0, leftBorderSum = 0;
        for (int i = left; i >= 0; i--) {
            leftBorderSum += nums[i];
            if (leftBorderSum > maxLeftBorderSum) {
                maxLeftBorderSum = leftBorderSum;
            }
        }
        return 0;

    }

    // dp
    public int maxSubArray3(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        } else if (n == 0) {
            return 0;
        }
        int[] f = new int[n];
        f[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < n; i++) {

            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            res = Math.max(res, f[i]);
        }
        return res;
    }


    // 贪心
    public int maxSubArray4(int[] nums) {

        int res = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            res = Math.max(sum, res);
            if (sum < 0) {
                sum = 0;
            }
        }
        return res;
    }
}
